import java.util.ArrayList;

public class LC0151 {
    public static String reverseWords(String s) {
        String[] subStrings = s.split(" ");

        StringBuilder sb = new StringBuilder();
        for (int i = subStrings.length - 1; i >= 0; i--) {
            if (!subStrings[i].isEmpty()) {
                if (!sb.isEmpty()) sb.append(" ");
                sb.append(subStrings[i]);
            }
        }

        return sb.toString();
    }

    /**
     * “假的”O(1)空间复杂度解法，因为String转charArray需要O(N)复杂度的空间。
     * 主要思想是先反转整个字符串，再反转每个单词。
     */
    public static String reverseWordsConstSpace(String s) {
        char[] charArray = s.toCharArray();
        reverse(charArray, 0, charArray.length);

        int length = charArray.length;

        // 求起始（含）和结尾（含）索引
        /*int start = -1;
        int end = -1;
        for (int i = 0; i < length; i++) {
            if (charArray[i] != ' ') {
                start = i;
                break;
            }
        }
        for (int j = length - 1; j >= 0; j--) {
            if (charArray[j] != ' ') {
                end = j;
                break;
            }
        }*/

        // 将单词逐个取反
        int writeIdx = 0; // 写入位置
        int start, end = length; // 单词的开头和结尾位置
        for (int idx = 0; idx < length; ) { // 遍历字符数组使用的指针
            if (charArray[idx] != ' ') { // idx指向非空字符
                if (writeIdx != 0) { // 如果writeIdx不位于起始位置，则插入空格
                    charArray[writeIdx++] = ' ';
                }
                start = writeIdx;
                while (idx < length && charArray[idx] != ' ') { // 单词前移
                    charArray[writeIdx++] = charArray[idx++];
                } // 现在idx位于结尾或空格上，writeIdx位于单词结束后一个位置
                end = writeIdx;

                reverse(charArray, start, end);
            }
            else {
                idx++;
            }
        }

        // 舍弃末尾的字符（需要的字符已经全部前移）
        String retString = new String(charArray);
        return retString.substring(0, end); // end位于最后一个单词的后一个位置（题目保证一定存在至少一个单词）
    }

    private static void reverse(char[] charArray, int start, int end) {
        // 反转整个字符数组
        for (int i = start; i < start + (end - start) / 2; i++) {
            char tmp = charArray[i];
            int j = end - 1 - (i - start); // 右侧对称位置的索引
            charArray[i] = charArray[j];
            charArray[j] = tmp;
        }
    }

    public static void main(String[] args) {
        String s = "  a good   example  ";
        System.out.println(reverseWordsConstSpace(s));
    }
}
